Various discovery protocols have been proposed to enable a device (e.g., a user-operated device) to discover other devices and services on managed and unmanaged (ad-hoc) networks, without prior knowledge of the other devices and services. Examples include the Service Location Protocol, version 2 (SLPv2), described in Guttman et al., “Service Location Protocol, Version 2,” IETF RFC 2608, June 1999; Rendevous by Apple Computer, Inc., described in Chesire, “DNS-based Service Discovery,” IETF Internet Draft, December 2002 and Chesire, “Performing DNS queries via IP Multicast,” IETF Internet Draft, December 2002; and the Simple Service Discovery Protocol (SSDP), described in Goland et al., “Simple Service Discovery Protocol/1.0, Operating without an Arbiter,” IETF Internet Draft, April 2000. For various reasons, these other discovery protocols suffer limitations as to reliability, security and scalability.